/*
 * @lc app=leetcode.cn id=372 lang=typescript
 *
 * [372] 超级次方
 */

// @lc code=start
function superPow(a: number, b: number[]): number {
  // 快速幂
  const power = (base: number, n: number): number => {
    base = base % mod;
    let res = 1;
    while (n !== 0) {
      if (n & 1) res = (res * base) % mod;
      base = (base * base) % mod;
      n >>= 1;
    }
    return res;
  };

  let mod = 1337;
  let base = a % mod;
  let ans = 1;
  // a^12分解为(a^2)*(a^10)^1
  for (let i = b.length - 1; i >= 0; i--) {
    ans = (ans * power(base, b[i])) % mod;
    base = power(base, 10);
  }

  return ans;
}
// @lc code=end
